contents

🌀 코딩 테스트를 위한 재귀(Recursion) & 백트래킹(Backtracking) 가이드

여기서는 개념, 차이점, 대표 문제 유형, Java 스타일 코드 예제로 재귀와 백트래킹을 깊이 있게 정리합니다.

1. 재귀(Recursion)란?

정의:
함수가 자기 자신을 호출하여 문제를 더 작은 하위 문제로 쪼개어 해결하는 기법입니다.

• 핵심 원리: 큰 문제를 동일한 성질의 작은 문제로 나눠서 풀고, **기저 조건(Base Case)**에서 종료.
• 대표 예시: 팩토리얼, 피보나치, 트리 순회

예제 – 팩토리얼

int factorial(int n) {
    if (n == 0) return 1;          // 기저 조건
    return n * factorial(n - 1);   // 재귀 호출
}

Dry Run (n=3):

• factorial(3) → 3 * factorial(2)
• factorial(2) → 2 * factorial(1)
• factorial(1) → 1 * factorial(0)
• factorial(0) → 1
• 최종값: 6

2. 백트래킹(Backtracking)이란?

정의:
모든 가능한 경우의 수(선택지)를 탐색하면서, 조건에 맞지 않으면 되돌아가서(Backtrack) 다른 길을 찾는 방식의 재귀 탐색 기법입니다.

• 핵심 원리: 가능한 선택지를 재귀적으로 모두 시도 → 실패 시 이전 상태로 복원(undo) 후 다른 가지(branch) 탐색.
• 대표 문제: N-Queen, 스도쿠, 부분집합, 순열, 단어 찾기

3. 재귀 vs 백트래킹

• 공통점: 둘 다 함수가 자기 자신을 호출하는 구조.
• 차이점:
  • 재귀는 보통 한 해답이나 값을 구함.
  • 백트래킹은 여러 해답/모든 경우의 수를 탐색 + 제약 조건을 만족하는 해만 선택.

4. 대표 백트래킹 문제 & 코드

a. N-Queen 문제

void solveNQueens(int n) {
    List<List<String>> solutions = new ArrayList<>();
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(board, 0, solutions);
}

void backtrack(char[][] board, int row, List<List<String>> solutions) {
    if (row == board.length) {
        solutions.add(boardToList(board));
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrack(board, row + 1, solutions);
            board[row][col] = '.'; // 상태 복원
        }
    }
}

boolean isValid(char[][] board, int row, int col) {
    for (int i = 0; i < row; i++)
        if (board[i][col] == 'Q') return false;
    for (int i = row-1, j = col-1; i>=0 && j>=0; i--, j--)
        if (board[i][j] == 'Q') return false;
    for (int i = row-1, j = col+1; i>=0 && j<board.length; i--, j++)
        if (board[i][j] == 'Q') return false;
    return true;
}

b. 스도쿠 해결

boolean solveSudoku(char[][] board) {
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if (board[i][j] == '.') {
                for (char c = '1'; c <= '9'; c++) {
                    if (isValid(board, i, j, c)) {
                        board[i][j] = c;
                        if (solveSudoku(board)) return true;
                        board[i][j] = '.'; // 백트래킹
                    }
                }
                return false;
            }
    return true;
}

boolean isValid(char[][] b, int r, int c, char num) {
    for (int i = 0; i < 9; i++) {
        if (b[r][i] == num || b[i][c] == num) return false;
        if (b[3*(r/3)+i/3][3*(c/3)+i%3] == num) return false;
    }
    return true;
}

c. 부분집합 생성

List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

void backtrack(int[] nums, int start, List<Integer> track, List<List<Integer>> res) {
    res.add(new ArrayList<>(track));
    for (int i = start; i < nums.length; i++) {
        track.add(nums[i]);
        backtrack(nums, i+1, track, res);
        track.remove(track.size()-1);
    }
}

d. 순열 생성

List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, new ArrayList<>(), new boolean[nums.length], res);
    return res;
}

void backtrack(int[] nums, List<Integer> track, boolean[] used, List<List<Integer>> res) {
    if (track.size() == nums.length) {
        res.add(new ArrayList<>(track));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (!used[i]) {
            track.add(nums[i]);
            used[i] = true;
            backtrack(nums, track, used, res);
            track.remove(track.size()-1);
            used[i] = false;
        }
    }
}

e. 단어 찾기 (Word Search)

boolean exist(char[][] board, String word) {
    for (int i = 0; i < board.length; i++)
        for (int j = 0; j < board[0].length; j++)
            if (dfs(board, word, i, j, 0)) return true;
    return false;
}

boolean dfs(char[][] board, String word, int i, int j, int idx) {
    if (idx == word.length()) return true;
    if (i<0 || j<0 || i>=board.length || j>=board[0].length || board[i][j] != word.charAt(idx))
        return false;

    char tmp = board[i][j];
    board[i][j] = '#';
    boolean found = dfs(board, word, i+1, j, idx+1) ||
                    dfs(board, word, i-1, j, idx+1) ||
                    dfs(board, word, i, j+1, idx+1) ||
                    dfs(board, word, i, j-1, idx+1);
    board[i][j] = tmp; // 상태 복원
    return found;
}

5. 백트래킹 템플릿

void backtrack(...) {
    if (해답 조건 충족) {
        저장/출력;
        return;
    }
    for (가능한 선택 : 모든 후보) {
        if (조건 검증) {
            상태 변경;
            backtrack(...);
            상태 복원;
        }
    }
}

6. 핵심 팁

• 상태 추적: 배열, 리스트, visited[] 활용
• 가지치기(Pruning): 불가능한 경우는 일찍 버림
• 상태 복원: 재귀 호출 후 반드시 이전 상태로 되돌림
• 재귀트리: 각 노드가 하나의 상태 / 각 가지가 선택 경로

7. 사용 시점

• 모든 경우의 수/조합/순열 필요
• 제약 조건이 있는 문제(예: N-Queen)
• 미로·그래프 경로 찾기
• 의사결정 트리 생성, 중첩 구조 탐색

8. 복잡도

대부분 지수 시간 복잡도 O(kⁿ) 또는 O(n!)
→ 가지치기·메모이제이션으로 가능하면 줄이기

9. 요약 표

🔥 코딩 테스트 Recursion/Backtracking(재귀/백트래킹) 대표 문제 & 풀이 정리

아래는 LeetCode·프로그래머스·기업 면접 등에서 매우 자주 등장하는 재귀·백트래킹 유형 대표 문제와 기본 풀이 코드/핵심 아이디어를 정리한 내용입니다.

1. 모든 부분집합(Powerset) 구하기

문제:
정수 집합이 주어질 때, 모든 부분집합(파워셋)을 반환하세요.

풀이:
각 요소에 대해 “포함/불포함”을 선택하며 백트래킹(재귀 탐색).

void dfs(int[] nums, int idx, List<Integer> path, List<List<Integer>> res) {
    res.add(new ArrayList<>(path)); // 현재 부분집합 저장
    for (int i = idx; i < nums.length; i++) {
        path.add(nums[i]);
        dfs(nums, i+1, path, res); // 다음 단계로 이동
        path.remove(path.size()-1); // 백트래킹
    }
}

2. 순열(Permutations)

문제:
수열이 주어질 때, 가능한 모든 순열을 반환하세요.

풀이:
재귀 + used[] 배열로 중복 방지. 사용 안한 요소마다 새로운 자리에 시도.

void dfs(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> res) {
    if (path.size() == nums.length) res.add(new ArrayList<>(path));
    else {
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                used[i] = true;
                path.add(nums[i]);
                dfs(nums, path, used, res);
                path.remove(path.size()-1); // 백트래킹
                used[i] = false;
            }
        }
    }
}

3. N-Queen

문제:
N×N 체스판에 서로가 공격하지 않는 N개의 퀸을 배치하는 모든 경우(배치)를 반환하세요.

풀이:
각 행(row)마다 가능한 위치에 퀸을 놓고, 유효성 체크(열, 대각선).
퀸을 놓고 다음 행 진행, 불가능하면 되돌림 (백트래킹).

void dfs(char[][] board, int row, List<List<String>> res) {
    if (row == board.length) res.add(boardToList(board));
    else {
        for (int col = 0; col < board.length; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                dfs(board, row+1, res);
                board[row][col] = '.'; // 백트래킹
            }
        }
    }
}

4. 스도쿠(Sudoku) 풀이

문제:
9×9 스도쿠 퍼즐(공백: '.')을 채우세요.

풀이:
모든 셀에 1~9 숫자 시도, 유효(행/열/칸 체크)하면 재귀 진행, 불가능하면 되돌림.

boolean solve(char[][] board) {
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++)
            if (board[r][c] == '.') {
                for (char num = '1'; num <= '9'; num++)
                    if (isValid(board, r, c, num)) {
                        board[r][c] = num;
                        if (solve(board)) return true;
                        board[r][c] = '.'; // 백트래킹
                    }
                return false;
            }
    return true;
}

5. Word Search (단어찾기/격자 경로찾기)

문제:
2차원 문자판(board)과 단어(word)가 주어질 때, 인접(상하좌우) 셀을 따라 해당 단어를 완성할 수 있는지 판별하세요.

풀이:
모든 셀 시작점에서 DFS+백트래킹. 방문체크, 네 방향 재귀, 실패 시 원상복구.

boolean dfs(char[][] board, String word, int i, int j, int idx) {
    if (idx == word.length()) return true;
    if (i<0 || j<0 || i>=board.length || j>=board[0].length || board[i][j] != word.charAt(idx)) return false;
    char tmp = board[i][j]; board[i][j] = '#';
    boolean found = dfs(board, word, i+1, j, idx+1) ||
                    dfs(board, word, i-1, j, idx+1) ||
                    dfs(board, word, i, j+1, idx+1) ||
                    dfs(board, word, i, j-1, idx+1);
    board[i][j] = tmp; return found;
}

6. Combination Sum / Subset Sum

문제:
정수 candidates와 target이 주어질 때, 각 원소를 여러 번 사용할 수 있는 합이 target이 되는 모든 조합을 구하세요.

풀이:
각 원소를 고르거나, 스킵하거나. 선택시 target 감소, 백트래킹.

void dfs(int[] candidates, int target, int idx, List<Integer> path, List<List<Integer>> res) {
    if (target == 0) res.add(new ArrayList<>(path));
    else if (target > 0) {
        for (int i = idx; i < candidates.length; i++) {
            path.add(candidates[i]);
            dfs(candidates, target-candidates[i], i, path, res); // 같은 값 재사용 허용
            path.remove(path.size()-1); // 백트래킹
        }
    }
}

7. 올바른 괄호 조합 생성 (Generate Parentheses)

문제:
N쌍의 괄호(N pairs)가 주어질 때, 모든 올바른 조합을 생성하세요.

풀이:
왼쪽 괄호(open), 오른쪽 괄호(close) 개수를 추적. open < N이면 '(', close < open이면 ')' 추가. 길이=2N이면 기록.

void dfs(int n, int open, int close, String path, List<String> res) {
    if (path.length() == 2*n) res.add(path);
    if (open < n) dfs(n, open+1, close, path+"(", res);
    if (close < open) dfs(n, open, close+1, path+")", res);
}

✅ 면접/코테 채점 포인트 요약

💡 팁

• 항상 **기저 조건, 재귀 호출, 되돌림(상태 복구)**을 강조하세요.
• 효율화를 위한 가지치기, 방문 체크 등도 반드시 설명!
• 손코딩 예시나 재귀트리 모식도도 보여주면 더 좋습니다.

references